package com.cwj.课程设计;

import com.cwj.lab4.Tool;

import java.util.Comparator;

/**
 * 优先队列
 * 默认为大顶堆实现
 * */
public class PQueue<T extends Comparable<T>> {
    private Object[] nums;//存储元素
    private int len;//有效元素数目
    private Comparator<T>comparator;//比较器（可选）
//默认的数组长度为14
    public PQueue() {
        this(14);
    }
    public PQueue(int size){
        this(size,null);
    }
//    可自定义元素长度
    public PQueue(int len,Comparator<T>comparator) {
        this.len = 0;
        nums = new Object[len];
        this.comparator=comparator;
    }
//设置构造函数
    public void setComparator(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    //比较函数
    private int less(Object one, Object two) {
        if(this.comparator!=null){
            return comparator.compare((T)one,(T)two);
        }
        return ((T) one).compareTo((T) two);
    }
//元素上浮操作
    private void sink(int ind) {
        int parent = ind;
//        如果父亲节点不小于0，即为合法值
        while ((parent = (ind - 1) / 2) >= 0) {
            //如果父亲节点小于目前节点，就交换，否则就不交换
            if (less(this.nums[ind], this.nums[parent]) > 0) {
                Tool.swap(this.nums, ind, parent);
                ind = parent;
            } else {
                break;
            }
        }
    }
//元素下降操作
    private void swim(int ind, int end) {
        int lef = 0, rig = 0;
        //合法值进入，且如果子节点中较大的元素大于目前节点，那么就交换，继续进行重复计算
        while ((lef = (ind * 2 + 1)) <= end) {
            if ((rig = lef + 1) <= end && less(this.nums[lef], this.nums[rig]) < 0) {
                lef = rig;
            }
            if (less(this.nums[lef], this.nums[ind]) > 0) {
                Tool.swap(this.nums, lef, ind);
                ind = lef;
            } else {
                break;
            }
        }
    }
//插入元素
    public void insert(T one) {
        if (this.len + 1 >= this.nums.length) {
            resize();
        }
        this.nums[this.len] = one;
        this.len += 1;
        sink(this.len - 1);
    }
//删除元素
    public T pop() {
        this.len -= 1;
        Object oldVal = this.nums[0];
        this.nums[0] = this.nums[this.len];
        swim(0, this.len - 1);
        return (T) oldVal;
    }
//扩容操作
    public void resize() {
        resize(this.nums.length * 3 / 2);
    }

    public void resize(int newSize) {
        if (newSize < 0) {
            throw new RuntimeException("newSize不能为零");
        }
        if (this.nums == null) {
            this.nums = new Object[newSize];
        } else {
            //如果要扩容的数值比原有数值小，那么就默认扩3/2;
            if (this.nums.length > newSize) {
                newSize = this.nums.length * 3 / 2;
            }
            //重新插入数据
            Object[] newNums = new Object[newSize];
            for (int i = 0; i < this.len; i++) {
                newNums[i] = this.nums[i];
            }
            this.nums = newNums;
        }
    }
//获取有效元素数目
    public int getLen() {
        return len;
    }
//是否为空
    public boolean isEmpty() {
        return this.len <= 0;
    }

    public static void main(String[] args) {
        PQueue<Integer> pq = new PQueue<>();
        int size = 50, val = 0;
        for (int i = 0; i < size; i++) {
            pq.insert(val = (int) (Math.random() * 20));
        }
    }
}
